1. Field of the Invention
The present invention relates to design verification in the digital computing field. More particularly, the present invention relates to a coverage analysis tool and method that manages the initiation and execution of multiple concurrent software monitors that run during simulation testing of a digital design.
2. Description of the Related Art
This application is related to U.S. patent app. Ser. No. 09/406,017, filed 24 Sep. 1999, now U.S. Pat. No. 6,889,180, entitled “Method and Apparatus for a Monitor that Detects and Reports a Status Event to a Database” (hereinafter, “the Monitor Patent”); U.S. patent app. Ser. No. 09/406,016, now U.S. Pat. No. 6,594,803, filed 24 Sep. 1999 (24 Sep.1999), entitled “Method and Apparatus that Reports Multiple Status Events with a Single Monitor” (hereinafter, “the Grid Patent”); and U.S. patent app. Ser. No. 09/966,049, now U.S. Pat. No. 7,099,812, filed 28 Sep. 2001, entitled “Grid That Tracks the Occurrence of a N-Dimensional Matrix of Combinatorial Events in a Simulation Using A Linear Index” (hereinafter, “the Grid Patent II”), all of which are incorporated by reference for all purposes into this specification and referred to collectively as “the related patents.”
As described in detail in the related patents, digital designs perform a finite number of logical functions or operations, either alone or in combinations, where each specific event or combination of events is called a state. For instance, a typical digital design such as a microprocessor might support four separate operations called addition (a), multiplication (m), subtraction (s), and division (d). Within each operation, different specific events may occur. For instance, addition of two negative numbers may occur, or addition of two positive numbers may occur. In more complex designs, events may happen serially so that the number of states is increased. For instance, the operation sequence addition-multiplication-division (amd) is a different state than the operation sequence addition-multiplication-subtraction (ams). More states exist in the digital design when each a, m, s, and d operation supports various types of operands (i.e., positive, negative, and zero). Each permutation combining possible specific events results in a different state.
The related patents describe the difficulty of verifying such modern digital designs, and explain that such verification difficulty results from the designs' ability to attain an almost incalculable number of states. Consequently, designers have developed methods that verify a subset of the (hopefully interesting) states achievable by a digital design. The subset of states verified is selected with an eye to achieving a reasonable degree of test coverage. To gain an adequate level of confidence that the design is functioning correctly, it is necessary to verify whether the design attains all of the interesting states in the subset during operation or simulation.
As discussed in the related patents, verification of digital designs is usually done using a simulator. A simulator is a program that runs the design file of a digital design in order to recreate how the design would perform on a computer chip. A common method for generating test stimulus is to use a random, or directed random, test case generator. Those skilled in the art understand the many advantages and few disadvantages of random test generation, some of which are briefly discussed in the related patents. In connection with one of the disadvantages of random testing, the related patents explain the need for coverage analysis tools that quantify the percentage of the existing design states that have been hit during random testing, and describe some of the difficulties with current coverage analysis tools and the coverage data that such current tools generate. The related patents then disclose tools and methods that can be used to monitor simulation-based verification testing of a digital design. The related patents describe, in general, a computer program called a monitor that checks a design under simulation for a set of specific, predefined verification events, and a computer program called a grid that checks a design for specific combinations of events. If the monitor or grid detects a specific event or combination of events, that information is reported to a database.
The related patents describe how monitors and grids are constructed using a monitor language that, in a preferred embodiment, uses existing C++ constructs as an initial foundation, and adds a set of keywords that simplify the identification of the types of verification events that a monitor or grid will need to examine. The monitor language provides a straightforward method for a user to create a software monitor or grid that is easily converted by a parser into a standard higher-order software language such as the C++ language. The C++ code is then compiled and dynamically or statically linked into the simulation environment. The simulation environment includes software that evaluates each monitor during every simulation cycle and tracks how many times each monitor evaluates to true during a simulation. At the end of the simulation, the simulation environment summarizes this coverage information and logs it in a database for future analysis.
The monitor language keywords support the construction of monitors and grids that are capable of detecting whether certain specified events occur at all, whether two or more specified events occur simultaneously, and whether two or more events occur during a specified time period or in a specific order during a specified time period. For example, the related patents describe how the keyword assert is used to check whether a logic expression is true. If an expression is true, execution of The monitor continues. If false, execution is halted and an error condition is flagged. The related patents also describe the use of the keywords wait and expect. Wait statements stall the execution of the monitor for a predetermined number of clock cycles to allow for the observation of design behavior over the stall period. Expect statements provide a time window within which an expression is tested. If the expression evaluates true within the time window, the monitor continues execution. If the expression does not evaluate true during the time window, the monitor exits without recording a hit. These capabilities present challenges in a typical simulation of a complex digital design, where, during a given time window, dozens of different processor states of interest are possible. To detect these different interesting states, a developer might need to have several monitors or grids executing simultaneously, some of which will include time-dependent verification events such as those described above. However, it is generally not feasible, from a computing resource standpoint, to run a monitored simulation that includes a number of monitors or grids executing in multiple, simultaneous execution threads. While execution threads can provide a handy way to either share parts of a program across multiple processing units or to suspend execution of code while waiting for an event, the multiple thread calls that would be required for the simultaneous execution of multiple monitors, particularly those that include time dependencies, would result in an unacceptable performance cost.
To illustrate the problem, consider a monitor A set up to detect the situation where signal A holds certain value a, followed two cycles later by signal B holding certain value b in a cycle-based simulation of a processor. Assume further that the bulk of the cycle-based simulation comprises a call to one function that cycles the entire model. To detect the specified event, the simulation environment needs to somehow “remember” what has happened on previous cycles with respect to the value of signal A. When the simulation environment executes the monitor check function each cycle, the observed processor state is the state achieved during that cycle only. To detect the specified event, the simulation environment needs to maintain state information to remember what has happened on previous cycles.
Those skilled in the art will recognize that threads would solve the problem of maintaining the state observed by the monitor. The monitor program could run until it needs to wait a cycle to proceed. The operating system would then be called to suspend the thread until after the next call to the cycle-based simulator. In this way the state of the monitor program would be preserved from cycle to cycle.
Continuing with the above example, suppose monitor A detects that at time T0, signal A holds value a. It now needs to wait two cycles and then check the value of signal B. One way to accomplish this is to use a semaphore. After monitor A finds that signal A=a during a cycle, the semaphore “stalls” execution of the thread for the proper amount of time (2 cycles in this example), at which time execution can resume and the value of signal B can be checked. Unfortunately, this process requires a minimum of two thread calls every processor cycle while the semaphore is active: the first, which calls the function that steps the simulator to the next cycle, and the second, which calls the monitor to check whether the semaphore has timed out.
Expanding the problem, suppose that at time T1, signal A again holds value a, and that at time T3, 2 cycles later, signal B holds value b. This is the event that monitor A is set up to detect. However, as described above, monitor A was stalled at time T1, waiting for the appropriate time to elapse after T0 to check the value of signal B. If monitor A is the only instance of the example monitor that is running during the simulation, the event that the processor designer wants to detect will go unnoticed. To avoid this situation, another instance of monitor A must be executing during the simulation to check the value of signal A at time T1. As this example demonstrates, it is difficult to achieve 100% detection of time-based verification events in a simulation using threads and semaphores. One way to insure detection is to initiate a new instance of monitor A every cycle of the simulation. Another way is to track the status of existing executing monitors, and initiate new instances only when all current instances are stalled or otherwise unable to check for their conditions of interest. Either approach could potentially result in hundreds of execution threads, particularly in a simulation where multiple monitors are desired to detect different time-based verification events, requiring potentially hundreds of thread calls every cycle. Because of the multiple instances required, this thread-based approach yields such a severe performance penalty that it is unusable, even for simulations where only one monitor containing time-dependent verification events is implemented. Running a simulation that includes the simultaneous execution of multiple time-dependent monitors in this manner is clearly out of the question.
The present invention solves this problem. The present invention comprises a monitor manager used in the simulation environment that first creates executable monitors and grids from the monitors and grids described in the high-level monitor language, then schedules and manages the efficient execution of the required instances of each monitor and grid during the simulation, and finally, maintains hit statistics. The monitor manager converts each monitor and grid that includes time-dependent verification events into a state machine capable of suspending execution for a time, and then resuming execution at the point where it “left off.” This state machine approach enables time-dependent monitors to be executed without using threads, thus avoiding the enormous overhead associated with thread calls. In addition, the monitor manager avoids the need for redundant creation and execution of identical instances of monitors and grids to insure 100% detection of specified verification events.